#合并k个升序链表
import heapq
from typing import List, Optional


# 定义链表节点
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        count = 0  # 用于处理节点值相同时的比较冲突
        # 初始化堆，将所有链表的头节点放入堆
        for node in lists:
            if node:
                heapq.heappush(heap, (node.val, count, node))
                count += 1

        dummy = ListNode(-1)
        current = dummy

        # 不断从堆中取出最小节点
        while heap:
            val, cnt, node = heapq.heappop(heap)
            current.next = node
            current = current.next
            if node.next:
                heapq.heappush(heap, (node.next.val, count, node.next))
                count += 1

        return dummy.next


# 列表转链表的工具函数
def list_to_linked_list(lst: List[int]) -> Optional[ListNode]:
    dummy = ListNode(-1)
    current = dummy
    for num in lst:
        current.next = ListNode(num)
        current = current.next
    return dummy.next


# 链表转列表的工具函数（用于验证结果）
def linked_list_to_list(head: Optional[ListNode]) -> List[int]:
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result


if __name__ == "__main__":
    # 测试用例
    solution = Solution()

    # 示例1
    lists1 = [
        list_to_linked_list([1, 4, 5]),
        list_to_linked_list([1, 3, 4]),
        list_to_linked_list([2, 6])
    ]
    merged1 = solution.mergeKLists(lists1)
    print(linked_list_to_list(merged1))  # [1,1,2,3,4,4,5,6]

    # 示例2（空列表）
    lists2 = []
    merged2 = solution.mergeKLists(lists2)
    print(linked_list_to_list(merged2))  # []

    # 示例3（包含空链表）
    lists3 = [list_to_linked_list([])]
    merged3 = solution.mergeKLists(lists3)
    print(linked_list_to_list(merged3))  # []